package LeetCode.leetcode22;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateParenthesis(int n) {
        //()
        int[] rest = new  int[]{n,n};
        List<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        backTracking(n, res, rest, sb);
        return res;
        
    }
    public void backTracking(int n, List<String> ans, int[] rest, StringBuilder sb) {
        if (rest[0]<= 0 && rest[1] <= 0){
            ans.add(new String(sb));
            return;
        }
        if (rest[0] > 0){
            rest[0]--;
            sb.append('(');
            backTracking(n,ans,rest,sb);
            sb.deleteCharAt(sb.length()-1);
            rest[0]++;
        }
        if (rest[1] > 0 && rest[0] < rest[1]){
            rest[1]--;
            sb.append(')');
            backTracking(n,ans,rest,sb);
            sb.deleteCharAt(sb.length()-1);
            rest[1]++;
        }
    }
}